public class BinarySearchTree {

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root = null;

    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val > key) {
                cur = cur.left;
            } else
                return cur;
        }
        return null;
    }

    public void insert(int key) {
        TreeNode node = new TreeNode(key);
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                return;
            }
        }
        //次循环走完，parent 指向的节点就是需要插入的节点位置的父亲节点
        if (parent.val > key) {
            parent.left = node;
        } else if (parent.val < key) {
            parent.right = node;
        } else {
            return;
        }
    }

    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                //此时就是找到了要删除的节点
                removeNode(parent, cur);
                return;
            }
        }
    }

    private void removeNode(TreeNode parent, TreeNode cur) {
        // 1.当要删除的节点 cur 的左孩子为空
        if (cur.left == null) {
            if (cur == root) {
                // 1.1 要删除的 cur 为根节点
                root = cur.right;
            } else if (cur == parent.left) {
                // 1.2 要删除的 cur 是 parent 的左节点
                parent.left = cur.right;
            } else {
                // 1.3 要删除的 cur 是 parent 的右节点
                parent.right = cur.right;
            }

            // 2. 要删除的节点 cur 的右孩子为空
        } else if (cur.right == null) {
            if (cur == root) {
                // 2.1 要删除的 cur 是根节点
                root = cur.left;
            } else if (cur == parent.left) {
                // 2.2 要删除的 cur 是 parent 的左节点
                parent.left = cur.left;
            } else {
                // 2.3 要删除的 cur 是 parent 的右节点
                parent.right = cur.left;
            }

            // 3. 要删除的节点的左右孩子都不为空
        } else {
            // 3.1 右数的最小值
            TreeNode t = cur.right;
            TreeNode tp = cur;
            while (t.left != null) {
                tp = t;
                t = tp.left;
            }
            cur.val = t.val;
            if(t == tp.right) {
                //t 和 tp 在起始步就找到了最小值
                tp.right = t.right;
            }else{
                //t 和 tp 在继续移动的过程中找到最小值
                tp.left = t.right;
            }
        }
    }
}
